package com.maozzi.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合
 *
 * @author maozi
 */
public class Combine {

    public static void main(String[] args) {

//        letterCombinations("");
//        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
//        System.out.println(combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
//        System.out.println(partition("aab"));
//        System.out.println(restoreIpAddresses("25525511135"));
//        System.out.println(subsets(new int[]{1, 2, 3}));
        System.out.println(subsetsWithDup(new int[]{1, 2, 2}));
    }

    /**
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * <p>
     * 你可以按 任何顺序 返回答案。
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        combineF(list, new ArrayList<>(), n, k, 1);
        return list;
    }

    /**
     * 未优化
     */
    public void combineF(List<List<Integer>> list, List<Integer> child, int n, int k, int start) {
        if (child.size() == k) {
            list.add(new ArrayList<>(child));
            return;
        }
        for (int i = start; i <= n; i++) {
            child.add(i);
            combineF(list, child, n, k, i + 1);
            child.remove(child.size() - 1);
        }
    }

    /**
     * 优化剪枝后
     */
    public void combineF1(List<List<Integer>> list, List<Integer> child, int n, int k, int start) {
        if (child.size() == k) {
            list.add(new ArrayList<>(child));
            return;
        }
        // k - child.size() ：需要的个数
        for (int i = start; i <= n - (k - child.size()) + 1; i++) {
            child.add(i);
            combineF(list, child, n, k, i + 1);
            child.remove(child.size() - 1);
        }
    }

    /**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     * <p>
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     */
    public static List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        String[] arr = new String[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            char c = digits.charAt(i);
            if (c == '2') {
                arr[i] = "abc";
            } else if (c == '3') {
                arr[i] = "def";
            } else if (c == '4') {
                arr[i] = "ghi";
            } else if (c == '5') {
                arr[i] = "jkl";
            } else if (c == '6') {
                arr[i] = "mno";
            } else if (c == '7') {
                arr[i] = "pqrs";
            } else if (c == '8') {
                arr[i] = "tuv";
            } else if (c == '9') {
                arr[i] = "wxyz";
            }
        }
        letterCombineF(list, new StringBuilder(), arr, digits.length(), 0);
        return list;
    }

    private static void letterCombineF(List<String> list, StringBuilder child, String[] arr, int k, int start) {
        if (child.length() == k && k != 0) {
            list.add(child.toString());
            return;
        }
        for (int i = start; i < arr.length; i++) {
            String temp = arr[i];
            for (int j = 0; j < temp.length(); j++) {
                child.append(arr[i].charAt(j));
                letterCombineF(list, child, arr, k, i + 1);
                child.deleteCharAt(child.length() - 1);
            }
        }
    }

    /**
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
     * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * <p>
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSum(list, new ArrayList<>(), candidates, target, 0, 0);
        return list;
    }

    public static void combinationSum(List<List<Integer>> list, List<Integer> child, int[] arr, int target, int start, int sum) {
        if (sum == target) {
            list.add(new ArrayList<>(child));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            if (sum + arr[i] > target) {
                break;
            }
            child.add(arr[i]);
            combinationSum(list, child, arr, target, i, sum + arr[i]);
            child.remove(child.size() - 1);
        }
    }


    /**
     * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * <p>
     * candidates 中的每个数字在每个组合中只能使用 一次 。
     * <p>
     * 注意：解集不能包含重复的组合。
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        combinationSum2(list, new ArrayList<>(), used, candidates, target, 0, 0);
        return list;
    }

    public static void combinationSum2(List<List<Integer>> list, List<Integer> child, boolean[] used, int[] arr, int target, int start, int sum) {
        if (sum == target) {
            list.add(new ArrayList<>(child));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            if (sum + arr[i] > target) {
                break;
            }
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            child.add(arr[i]);
            combinationSum2(list, child, used, arr, target, i + 1, sum + arr[i]);
            used[i] = false;
            child.remove(child.size() - 1);
        }
    }

    /**
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
     */
    public static List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        partition(list, new ArrayList<>(), s, 0);
        return list;
    }

    public static void partition(List<List<String>> list, List<String> child, String s, int start) {
        if (start >= s.length()) {
            list.add(new ArrayList<>(child));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isP(s.substring(start, i + 1))) {
                child.add(s.substring(start, i + 1));
            } else {
                continue;
            }
            partition(list, child, s, i + 1);
            child.remove(child.size() - 1);
        }
    }

    private static boolean isP(String s) {
        return s.contentEquals(new StringBuilder(s).reverse());
    }

    /**
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     * <p>
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
     * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
     * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
     */
    public static List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        if (s.length() > 12) {
            return list;
        }
        restoreIpAddresses(list, new ArrayList<>(), s, 0);
        return list;
    }

    public static void restoreIpAddresses(List<String> list, List<String> child, String s, int start) {
        if (start >= s.length() && child.size() == 4) {
            list.add(String.join(".", child));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (isIp(sub) && child.size() < 4) {
                child.add(sub);
            } else {
                continue;
            }
            restoreIpAddresses(list, child, s, i + 1);
            child.remove(child.size() - 1);
        }
    }

    private static boolean isIp(String s) {
        long i = Long.parseLong(s);
        return i >= 0 && i <= 255 && String.valueOf(i).equals(s);
    }

    /**
     * 给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        subsets(list, new ArrayList<>(), nums, 0);
        return list;
    }

    public static void subsets(List<List<Integer>> list, List<Integer> child, int[] nums, int start) {
        list.add(new ArrayList<>(child));
        if (start >= nums.length) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            child.add(nums[i]);
            subsets(list, child, nums, i + 1);
            child.remove(child.size() - 1);
        }
    }

    /**
     * 给你一个整数数组 nums ，其中可能包含重复元素。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        subsetsWithDup(list, new ArrayList<>(), nums, 0);
        return list;
    }

    public static void subsetsWithDup(List<List<Integer>> list, List<Integer> child, int[] nums, int start) {
        list.add(new ArrayList<>(child));
        if (start >= nums.length) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            child.add(nums[i]);
            subsetsWithDup(list, child, nums, i + 1);
            child.remove(child.size() - 1);
        }
    }
}
